package stanaGUI.KMeans;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;


public class AlgoKMeans {

	private int k;
	private final static Random random = new Random(System.currentTimeMillis());

	public AlgoKMeans(int k) {
		this.k = k;
	}

	/**
	 * 
	 * @param input
	 * @param k
	 *            :desired number of cluster
	 * @return
	 */
	
	
	public List<Cluster> runAlgorithm(List<stanaGUI.KMeans.Item> input) {
		List<Cluster> clusters = new ArrayList<Cluster>();

		// Special case : only one item
		if (input.size() == 1) {
			Item item = input.get(0);
			Cluster cluster = new Cluster(item);
			cluster.addItem(item);
			clusters.add(cluster);
			return clusters;
		}

		// (1) Randomly generate k empty clusters with a random median (cluster
		// center)

		// (1.1) Choose the higher and lower values for generating a median
		double higherVal1 = input.get(0).getValue1();
		double lowerVal1 = input.get(0).getValue1();
		double higherVal2 = input.get(0).getValue2();
		double lowerVal2 = input.get(0).getValue2();
		
		for (Item item : input) {
			if (item.getValue1() > higherVal1) {
				higherVal1 = item.getValue1();
			}
			if (item.getValue1() < lowerVal1) {
				lowerVal1 = item.getValue1();
			}
			if (item.getValue2() > higherVal2) {
				higherVal2 = item.getValue2();
			}
			if (item.getValue2() < lowerVal2) {
				lowerVal2 = item.getValue2();
			}
		}

		// Special case : all items have the same values, so we return only one
		// cluster.
		if ((higherVal1 == lowerVal1) && (higherVal2 == lowerVal2) ){
			Cluster cluster = new Cluster(input);
			clusters.add(cluster);
			return clusters;
		}

		// (1.2) Generate the k empty clusters with random median
		for (int i = 0; i < k; i++) {
			// generate random median

			double medianVal1 = random.nextInt((int) (higherVal1 - lowerVal1)) + lowerVal1;
			double medianVal2 = random.nextInt((int) (higherVal2 - lowerVal2)) + lowerVal2;
			
			// create the cluster
			
			Cluster cluster = new Cluster(new Item(medianVal1, medianVal2));
			clusters.add(cluster);
		}

		// (2) Repeat the two next steps until the assignment hasn't changed
		boolean changed;

		do {
			changed = false;
			// (2.1) Assign each point to the nearest cluster center.

			// / for each item
			for (Item item : input) {
				// find the nearest cluster and the cluster containing the item
				Cluster nearestCluster = null;
				Cluster containingCluster = null;
				double distanceToNearestCluster = Double.MAX_VALUE;

				for (Cluster cluster : clusters) {
					double distance = medianDistance(cluster, item);
					if (distance < distanceToNearestCluster) {
						nearestCluster = cluster;
						distanceToNearestCluster = distance;
					}
					if (cluster.containsItem(item)) {
						containingCluster = cluster;
					}
				}

				if (containingCluster != nearestCluster) {
					if (containingCluster != null) {
						removeItem(containingCluster.getItems(), item);
					}
					nearestCluster.addItem(item);
					changed = true;
				}
			}

			// (2.2) Recompute the new cluster medians
			for (Cluster cluster : clusters) {
				cluster.recomputeClusterMedian();
			}

		} while (changed);

		// Computer min and max for all clusters
		for (Cluster cluster : clusters) {
			cluster.computeHigherAndLower();
		}

		return clusters;
	}

	private void removeItem(List<Item> items, Item item) {
		for (int i = 0; i < items.size(); i++) {
			if (items.get(i) == item) {
				items.remove(i);
			}
		}
	}

	private double medianDistance(Cluster cluster1, Item item) {
		double median1 = Math.abs((cluster1.getMedianVal1() - item.getValue1()) );
		double median2 = Math.abs((cluster1.getMedianVal2() - item.getValue2()) );
		double returnVal = 0;
		if (median1 > median2)
			returnVal = median1;
		else
			returnVal = median2;
		return returnVal;
	}

	public void setK(int k) {
		this.k = k;
	}
}
